home *** CD-ROM | disk | FTP | other *** search
/ Ham Radio 2000 / Ham Radio 2000.iso / ham2000 / tcp_ip / os2 / pmnos11s / lzw.c < prev    next >
C/C++ Source or Header  |  1993-07-30  |  15KB  |  574 lines
  1. /*        SM0RGV data compression routines.
  2.  * This file implements the Lempel-Ziv Welch (LZW) data compression
  3.  * algorithm but with a variable code size, as in GIF format files.
  4.  *
  5.  * Copyright 1990 by Anders Klemets, SM0RGV. Permission granted for
  6.  * non-commercial distribution only.
  7.  */
  8.  
  9. #include "usock.h"
  10. #include <ctype.h>
  11. #include "global.h"
  12. #include "config.h"
  13. #ifdef    LZW
  14. #include "mbuf.h"
  15. #include "proc.h"
  16. #include "lzw.h"
  17. #include "socket.h"
  18. #include "session.h"
  19. #include "cmdparse.h"
  20.  
  21. static void fastencode __ARGS((struct usock *up,char data));
  22. static void morebits __ARGS((struct lzw *lzw));
  23. static void cleartbl __ARGS((struct lzw *lzw));
  24. static void addtobuffer __ARGS((struct usock *up,int32 code));
  25. static void addchar __ARGS((char data,struct lzw *lzw));
  26. static void getstring __ARGS((int32 code,struct lzw *lzw));
  27. static char firstchar __ARGS((int32 code,struct lzw *lzw));
  28. static void decodetbl __ARGS((int32 code,struct lzw *lzw));
  29. static int32 nextcode __ARGS((struct usock *up));
  30.  
  31. int
  32. dolzw(argc,argv,p)
  33. int argc;
  34. char *argv[];
  35. void *p;
  36. {
  37.     if(argc > 1) {
  38.         switch(tolower(*argv[1])) {
  39.         case 'm':
  40.             if(argc == 2) {
  41.                 tprintf("LZW mode: %s\n",Lzwmode ? "fast" : "compact");
  42.             } else {
  43.                 Lzwmode = (tolower(*argv[2]) == 'f');
  44.             }
  45.             return 0;
  46.         case 'b':
  47.             argc--;
  48.             argv++;
  49.             return setintrc(&Lzwbits,"LZW bits",argc,argv,9,16);
  50.         case '=':
  51.             if(argc == 3) {
  52.                 struct session *sp;
  53.                 if((sp = sessptr(argv[2])) != NULLSESSION) {
  54.                     lzwinit(sp->s,Lzwbits,Lzwmode);
  55.                 }
  56.             }
  57.             return 0;
  58.         }
  59.     }
  60.     tputs("Usage: lzw <mode|bits>\n");
  61.     return -1;
  62. }
  63.  
  64. /* Initialize a socket for compression. Bits specifies the maximum number
  65.  * of bits per codeword. The input and output code tables might grow to
  66.  * about (2^bits * 3) bytes each. The bits parameter does only serve as a
  67.  * recommendation for the decoding, the actual number of bits may be
  68.  * larger, but not never more than 16.
  69.  */
  70. void
  71. lzwinit(s,bits,mode)
  72. int s;        /* socket to operate on */
  73. int bits;    /* maximum number of bits per codeword */
  74. int mode;    /* compression mode, LZWCOMPACT or LZWFAST */
  75. {
  76.     struct usock *up;
  77.     if((up = itop(s)) == NULLUSOCK)
  78.         return;
  79.     up->zout = (struct lzw *) callocw(1,sizeof(struct lzw));
  80.     up->zin = (struct lzw *) callocw(1,sizeof(struct lzw));
  81.     up->zout->codebits = LZWBITS;
  82.     if(bits < LZWBITS)
  83.         up->zout->maxbits = LZWBITS;
  84.     if(bits > 16 || bits == 0)
  85.         up->zout->maxbits = 16;
  86.     if(bits >= LZWBITS && bits <= 16)
  87.         up->zout->maxbits = bits;
  88.     up->zout->nextbit = 0;
  89.     up->zout->prefix = -1;
  90.     up->zout->version = -1;
  91.     up->zout->code = -1;
  92.     up->zout->mode = mode;
  93.     up->zout->next = ZFLUSH + 1;    /* used only in LZWFAST mode */
  94.     up->zin->codebits = LZWBITS;
  95.     up->zin->maxbits = -1;
  96.     up->zin->nextbit = 0;
  97.     up->zin->prefix = -1;
  98.     up->zin->version = -1;
  99.     up->zin->code = -1;
  100.     up->zin->next = ZFLUSH + 1;
  101.     up->zin->mode = LZWCOMPACT;
  102.     up->zin->buf = NULLBUF;
  103. }
  104.  
  105. void
  106. lzwfree(up)
  107. struct usock *up;
  108. {
  109.     if(up->zout != NULLLZW) {
  110.         cleartbl(up->zout);
  111.         free((char *)up->zout);
  112.         up->zout = NULLLZW;
  113.     }
  114.     if(up->zin != NULLLZW) {
  115.         cleartbl(up->zin);
  116.         free_q(&up->zin->buf);
  117.         free((char *)up->zin);
  118.         up->zin = NULLLZW;
  119.     }
  120. }
  121. /* LZW encoding routine.
  122.  * See if the string specified by code + data is in the string table. If so,
  123.  * set prefix equal to the code of that string. Otherwise insert code + data
  124.  * in the string and set prefix equal to data.
  125.  */
  126. void
  127. lzwencode(int s, char data)
  128. {
  129.     struct usock *up;
  130.     register struct lzw *lzw;
  131.     int32 code, pagelim;
  132.     register unsigned int i,j;
  133.  
  134.     if((up = itop(s)) == NULLUSOCK)
  135.         return;
  136.     lzw = up->zout;
  137.     code = up->zout->prefix;
  138.     /* the first byte sent will be the version number */
  139.     if(lzw->version == -1) {
  140.         lzw->version = ZVERSION;
  141.         up->obuf->data[up->obuf->cnt++] = lzw->version;
  142.         /* then send our recommended maximum number of codebits */
  143.         up->obuf->data[up->obuf->cnt++] = lzw->maxbits;
  144.     }
  145.     lzw->cnt++;
  146.     if(code == -1) {
  147.         lzw->prefix = (int32) uchar(data);
  148.         return;
  149.     }
  150.     if(lzw->mode == LZWFAST) {
  151.         fastencode(up,data);
  152.         return;
  153.     }
  154.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  155.     if(code <= ZFLUSH)
  156.         i = j = 0;
  157.     else {
  158.         i = (code - ZFLUSH) / LZWBLK;
  159.         j = (code - ZFLUSH) % LZWBLK;
  160.     }
  161.     if(lzw->tu.tbl == (struct zentry **)0)
  162.         lzw->tu.tbl = (struct zentry **) callocw(1,
  163.             sizeof(struct zentry *) * pagelim);
  164.     for(;;) {
  165.         if(itop(s) == NULLUSOCK) /* the connection has been closed */
  166.             return;
  167.         if(up->zout == NULLLZW) /* ...or is about to be closed */
  168.             return;
  169.         if(lzw->tu.tbl[i] == (struct zentry *)0) {
  170.             lzw->tu.tbl[i] = (struct zentry *)
  171.                 mallocw(LZWBLK * sizeof(struct zentry));
  172.             memset((char *)lzw->tu.tbl[i], 0xff,
  173.                 LZWBLK * sizeof(struct zentry));
  174.         }
  175.         while(j < LZWBLK) {
  176.             if(lzw->tu.tbl[i][j].data == data &&
  177.                 lzw->tu.tbl[i][j].code == (int16) code) {
  178.                 lzw->prefix = (int32)(i * LZWBLK + j +
  179.                               ZFLUSH + 1);
  180.                 return;
  181.             }
  182.             if(lzw->tu.tbl[i][j].code == 0xffff) {
  183.                 lzw->tu.tbl[i][j].code = (int16) code;
  184.                 lzw->tu.tbl[i][j].data = data;
  185.                 addtobuffer(up,code);
  186.                 lzw->prefix = (int32) uchar(data);
  187.                 lzw->next++;
  188.                 if(lzw->next ==    (int32) 1 << lzw->codebits)
  189.                     /* the current table is now full */
  190.                     morebits(lzw);
  191.                 if(lzw->next + 1 == (int32)
  192.                         1 << lzw->maxbits) {
  193.                 /* The last codeword has been reached.
  194.                  * (Or last - 1.) Signal this and start all
  195.                  * over again.
  196.                  */
  197.                     addtobuffer(up,lzw->prefix);
  198.                        if(lzw->next + 1 == (int32)
  199.                             1 << lzw->codebits)
  200.                         morebits(lzw);
  201.                     addtobuffer(up,ZCC);
  202.                     cleartbl(lzw);
  203.                 }
  204.                 return;
  205.             }
  206.             ++j;
  207.         }
  208.         pwait(NULL);
  209.         ++i;
  210.         j = 0;
  211.     }
  212. }
  213.  
  214. /* Used when LZWFAST mode is selected. Memory usage approx. (2^bits * 5)
  215.  * bytes.
  216.  */
  217. static void
  218. fastencode(struct usock *up, char data)
  219. {
  220.     register struct zfast *z;
  221.     register struct mbuf *bp;
  222.     register struct lzw *lzw = up->zout;
  223.     int32 code = up->zout->prefix;
  224.     register int16 cnt, h;
  225.  
  226.     if(lzw->tu.bpp == NULLBUFP)
  227.         lzw->tu.bpp = (struct mbuf **) callocw(1,
  228.             sizeof(struct mbuf *) * ZHASH);
  229.     h = lobyte(code);
  230.     h ^= hibyte(code);
  231.     h ^= data;
  232.     h = h % ZHASH;
  233.     if(lzw->tu.bpp[h] == NULLBUF)
  234.         lzw->tu.bpp[h] = ambufw(LZWBLK);
  235.     bp = lzw->tu.bpp[h];
  236.     cnt = bp->cnt / sizeof(struct zfast);
  237.     z = (struct zfast *) bp->data;
  238.     while(cnt > 0) {
  239.         if(z->data == data && z->code == (int16) code) {
  240.             lzw->prefix = (int32) z->owncode;
  241.             return;
  242.         }
  243.         z++;
  244.         if(--cnt == 0) {
  245.             if(bp->next == NULLBUF)
  246.                 break;
  247.             bp = bp->next;
  248.             cnt = bp->cnt / sizeof(struct zfast);
  249.             z = (struct zfast *) bp->data;
  250.         }
  251.     }
  252.     if(bp->size - bp->cnt >= sizeof(struct zfast)) {
  253.         z = (struct zfast *) &bp->data[bp->cnt];
  254.         bp->cnt += sizeof(struct zfast);
  255.     }
  256.     else {
  257.         bp->next = ambufw(LZWBLK);
  258.         z = (struct zfast *) bp->next->data;
  259.         bp->next->cnt = sizeof(struct zfast);
  260.     }
  261.     z->code = (int16) code;
  262.     z->data = data;
  263.     z->owncode = (int16) lzw->next++;
  264.     addtobuffer(up,code);
  265.     lzw->prefix = (int32) uchar(data);
  266.     if(lzw->next == (int32) 1 << lzw->codebits) {
  267.         /* Increase the number of bits per codeword */
  268.         morebits(lzw);
  269.     }
  270.     if(lzw->next + 1 == (int32) 1 << lzw->maxbits) {
  271.         /* The last codeword has been reached. (Or last - 1.)
  272.          * Signal this and start all over again.
  273.          */
  274.         addtobuffer(up,lzw->prefix);
  275.         if(lzw->next + 1 == (int32) 1 << lzw->codebits)
  276.             morebits(lzw);
  277.         addtobuffer(up,ZCC);
  278.         cleartbl(lzw);
  279.     }
  280.     pwait(NULL);
  281. }
  282.  
  283. /* increase the number of significant bits in the codewords, and increase
  284.  * the size of the string table accordingly.
  285.  */
  286. static void
  287. morebits(lzw)
  288. struct lzw *lzw;
  289. {
  290.     struct zentry **newt;
  291.     int32 pagelim, oldp;
  292.     oldp = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  293.     lzw->codebits++;
  294.     if(lzw->mode == LZWFAST)
  295.         return;
  296.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  297.     newt = (struct zentry **) callocw(1,sizeof(struct zentry *)*pagelim);
  298.     memcpy(newt,lzw->tu.tbl,sizeof(struct zentry *) * oldp);
  299.     free((char *)lzw->tu.tbl);
  300.     lzw->tu.tbl = newt;
  301. }
  302.  
  303. static void
  304. cleartbl(lzw)
  305. struct lzw *lzw;
  306. {
  307.     int32 pagelim,i;
  308.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  309.     lzw->codebits = LZWBITS;
  310.     lzw->prefix = -1;
  311.     lzw->next = ZFLUSH + 1;
  312.     if(lzw->tu.p == NULL)
  313.         return;
  314.     if(lzw->mode == LZWCOMPACT)
  315.         for(i=0; i < pagelim; ++i)
  316.             free((char *)lzw->tu.tbl[i]);
  317.     else
  318.         for(i=0; i < ZHASH; ++i)
  319.             free_p(lzw->tu.bpp[i]);
  320.     free((char *)lzw->tu.p);
  321.     lzw->tu.p = NULL;
  322. }
  323. /* Add a codeword to the code stream. Nextbit indicates at which bit in the
  324.  * code stream should be written first. The codeword ZFLUSH is used to
  325.  * pad the buffer to a byte boundary when the buffer will be flushed.
  326.  * The remaining bits of the ZFLUSH codeword are sent in the next buffer.
  327.  */
  328. static void
  329. addtobuffer(up,code)
  330. struct usock *up;
  331. int32 code;
  332. {
  333.     if(up->zout->code != -1) {
  334.         /* Insert remaining bits of ZFLUSH codeword */
  335.         up->obuf->data[up->obuf->cnt] =
  336.              up->zout->code >> up->zout->flushbit;
  337.         if(up->zout->flushbit + 8 >= up->zout->codebits) { /* done */
  338.             up->zout->nextbit = (up->zout->codebits -
  339.                         up->zout->flushbit) % 8;
  340.             if(up->zout->nextbit == 0)
  341.                 ++up->obuf->cnt;
  342.             up->zout->code = -1;
  343.         }
  344.         else {
  345.             /* not done yet */
  346.             ++up->obuf->cnt;
  347.             up->zout->flushbit += 8;
  348.             addtobuffer(up,code);
  349.             return;
  350.         }
  351.     }
  352.     /* normal codewords are treated here */
  353.     if(up->zout->nextbit == 0) {
  354.         /* we are at a byte boundary */
  355.         if(code == ZFLUSH) {
  356.             up->zout->flushbit = 0;
  357.             up->zout->code = ZFLUSH;
  358.             return;
  359.         }
  360.         up->obuf->data[up->obuf->cnt++] = (char) code;
  361.     }
  362.     else
  363.         up->obuf->data[up->obuf->cnt++] |= code << up->zout->nextbit;
  364.     if(code == ZFLUSH) {
  365.         /* interrupt here and save the rest of the ZFLUSH
  366.          * codeword for later.
  367.          */
  368.         up->zout->flushbit = 8 - up->zout->nextbit;
  369.         up->zout->code = ZFLUSH;
  370.         return;
  371.     }
  372.     up->obuf->data[up->obuf->cnt] = code >> 8 - up->zout->nextbit;
  373.     /* start on a third byte if necessary */
  374.     if(16 - up->zout->nextbit < up->zout->codebits)
  375.         up->obuf->data[++up->obuf->cnt] =
  376.                     code >> 16 - up->zout->nextbit;
  377.     up->zout->nextbit = (up->zout->nextbit + up->zout->codebits) % 8;
  378.     if(up->zout->nextbit == 0)
  379.         ++up->obuf->cnt;
  380. }
  381.  
  382. void
  383. lzwflush(up)
  384. struct usock *up;
  385. {
  386.     /* interrupt the encoding process and send the prefix codeword */
  387.     if(up->zout->prefix != -1) {
  388.         addtobuffer(up,up->zout->prefix);
  389.            if(up->zout->next + 1 == (int32) 1 << up->zout->codebits)
  390.             morebits(up->zout);
  391.         up->zout->prefix = -1;
  392.     }
  393.     /* signal this by sending the ZFLUSH codeword */
  394.     addtobuffer(up,ZFLUSH);
  395. }
  396.  
  397. int
  398. lzwdecode(up)
  399. struct usock *up;
  400. {
  401.     int32 code,data;
  402.     if(up->zin->version == -1 && (up->zin->version = PULLCHAR(&up->ibuf))
  403.        == -1)
  404.         return -1;
  405.     if(up->zin->maxbits == -1) {
  406.         /* receive a recommended value for the maximum no of bits */
  407.         if((up->zin->maxbits = PULLCHAR(&up->ibuf)) == -1)
  408.             return -1;
  409.         if(up->zout->maxbits > up->zin->maxbits) {
  410.             if(up->zout->codebits > up->zin->maxbits) {
  411.                 /* We are already using more bits than our
  412.                  * peer want us to, so clear the encoding
  413.                  * table immediately.
  414.                  */
  415.                 addtobuffer(up,up->zout->prefix);
  416.                 if(up->zout->next + 1 == (int32)
  417.                    1 << up->zout->codebits)
  418.                     morebits(up->zout);
  419.                 addtobuffer(up,ZCC);
  420.                 cleartbl(up->zout);
  421.             }
  422.             up->zout->maxbits = up->zin->maxbits;
  423.         }
  424.     }
  425.     for(;;) {
  426.         if((data = PULLCHAR(&up->zin->buf)) != -1)
  427.             return (int) data;
  428.         if((code = nextcode(up)) == -1)
  429.             return -1;
  430.         decodetbl(code,up->zin);
  431.         up->zin->cnt += len_p(up->zin->buf);
  432.     }
  433. }
  434.  
  435. static void
  436. addchar(char data, struct lzw *lzw)
  437. {
  438.     lzw->buf = pushdown(lzw->buf,1);
  439.     *lzw->buf->data = data;
  440. }
  441. static void
  442. getstring(code,lzw)
  443. int32 code;
  444. struct lzw *lzw;
  445. {
  446.     int i,j;
  447.     for(;;) {
  448.         if(code < ZFLUSH) {
  449.             addchar(uchar(code),lzw);
  450.             return;
  451.         }
  452.         i = (code - ZFLUSH - 1) / LZWBLK;
  453.         j = (code - ZFLUSH - 1) % LZWBLK;
  454.         addchar(lzw->tu.tbl[i][j].data,lzw);
  455.         code = (int32) lzw->tu.tbl[i][j].code;
  456.     }
  457. }
  458. static char
  459. firstchar(code,lzw)
  460. int32 code;
  461. struct lzw *lzw;
  462. {
  463.     int i,j;
  464.     for(;;) {
  465.         if(code < ZFLUSH)
  466.             return uchar(code);
  467.         i = (code - ZFLUSH - 1) / LZWBLK;
  468.         j = (code - ZFLUSH - 1) % LZWBLK;
  469.         code = (int32) lzw->tu.tbl[i][j].code;
  470.     }
  471. }
  472. static void
  473. decodetbl(code,lzw)
  474. int32 code;
  475. struct lzw *lzw;
  476. {
  477.     register unsigned int i,j;
  478.     int32 pagelim;
  479.  
  480.     if(code > lzw->next) {
  481.         tprintf("LZW protocol error, process %s\n",Curproc->name);
  482.         return;
  483.     }
  484.     if(lzw->buf == NULLBUF) {
  485.         lzw->buf = ambufw(512);
  486.         /* allow us to use pushdown() later */
  487.         lzw->buf->data += lzw->buf->size;
  488.     }
  489.     if(lzw->prefix == -1) {
  490.         getstring(code,lzw);
  491.         lzw->prefix = code;
  492.         return;
  493.     }
  494.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  495.     if(lzw->tu.tbl == (struct zentry **)0)
  496.         lzw->tu.tbl = (struct zentry **) callocw(1,
  497.                 sizeof(struct zentry *) * pagelim);
  498.     if(code < ZFLUSH)
  499.         goto intable;
  500.     i = (code - ZFLUSH - 1) / LZWBLK;
  501.     j = (code - ZFLUSH - 1) % LZWBLK;
  502.     if(lzw->tu.tbl[i] == (struct zentry *)0) {
  503.         lzw->tu.tbl[i] = (struct zentry *)
  504.                 mallocw(LZWBLK * sizeof(struct zentry));
  505.         memset((char *)lzw->tu.tbl[i], 0xff,
  506.                 LZWBLK * sizeof(struct zentry));
  507.     }
  508.     if(lzw->tu.tbl[i][j].code == 0xffff) {
  509.         lzw->tu.tbl[i][j].data = firstchar(lzw->prefix,lzw);
  510.         lzw->tu.tbl[i][j].code = (int16) lzw->prefix;
  511.         getstring(code,lzw);
  512.         lzw->next = code + 1;
  513.         lzw->prefix = code;
  514.         if(lzw->next + 1 == (int32) 1 << lzw->codebits)
  515.             morebits(lzw);
  516.         return;
  517.     }
  518. intable:
  519.     getstring(code,lzw);
  520.     i = (lzw->next - ZFLUSH - 1) / LZWBLK;
  521.     j = (lzw->next - ZFLUSH - 1) % LZWBLK;
  522.     if(lzw->tu.tbl[i] == (struct zentry *)0) {
  523.         lzw->tu.tbl[i] = (struct zentry *)
  524.                 mallocw(LZWBLK * sizeof(struct zentry));
  525.         memset((char *)lzw->tu.tbl[i], 0xff,
  526.                 LZWBLK * sizeof(struct zentry));
  527.     }
  528.     lzw->tu.tbl[i][j].data = firstchar(code,lzw);
  529.     lzw->tu.tbl[i][j].code = (int16) lzw->prefix;
  530.     lzw->next++;
  531.     lzw->prefix = code;
  532.     if(lzw->next + 1 == (int32) 1 << lzw->codebits)
  533.         morebits(lzw);
  534. }
  535.  
  536. /* extract the next codeword from the input stream */
  537. static int32
  538. nextcode(up)
  539. struct usock *up;
  540. {
  541.     int32 code;
  542.     if(up->zin->code == -1) {    /* read the first character */
  543.         if((code = PULLCHAR(&up->ibuf)) == -1)
  544.             return -1;
  545.         up->zin->code = code >> up->zin->nextbit;
  546.     }
  547.     if(up->ibuf == NULLBUF)        /* next byte is not available yet */
  548.         return -1;
  549.     /* continue assembling the codeword */
  550.     up->zin->code |= ((int32) uchar(*up->ibuf->data) <<
  551.             8 - up->zin->nextbit) & (((int32) 1 <<
  552.             up->zin->codebits) - 1);
  553.     if(16 - up->zin->nextbit < up->zin->codebits) {
  554.         (void) PULLCHAR(&up->ibuf);
  555.         up->zin->nextbit -= 8; /* pull bits from a third byte */
  556.         return nextcode(up);
  557.     }
  558.     code = up->zin->code;
  559.     up->zin->code = -1;
  560.     up->zin->nextbit = (up->zin->nextbit + up->zin->codebits) % 8;
  561.     if(up->zin->nextbit == 0)
  562.         (void) PULLCHAR(&up->ibuf);
  563.     if(code == ZCC) {
  564.         cleartbl(up->zin);
  565.         return nextcode(up);
  566.     }
  567.     if(code == ZFLUSH) {
  568.         up->zin->prefix = -1;
  569.         return nextcode(up);
  570.     }
  571.     return code;
  572. }
  573. #endif
  574.